package 栈与队列;

import java.util.HashMap;
import java.util.Map;

/**
 * 106. 从中序与后序遍历序列构造二叉树
 *
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 *
 * 思路：
 *  中序遍历：左子树 -> 根节点 -> 右子树
 *  后续遍历：左子树 -> 右子树 -> 根节点
 *  因此，后续遍历的最后一个节点为根节点，根据中序遍历的特点，可以将后续遍历分为左右子树两部分，左子树的长度为左子树的节点个数，右子树的长度为右子树的节点个数。
 *解题步骤：
 * 1. 使用哈希表统计inorder中元素，方便快速定位到子树的根节点下标
 * 2：递归构造：
 *   终止条件：当数组为空时，返回null
 *   后序遍历的最后一个节点为根节点
 *   分割左右子树：
 *      根据中序遍历中根节点的位置，确认左右子树的区间；
 *      然后根据中序遍历和后序遍历的区间下标，递归构造左右子树
 * 3：返回根节点
 */
public class L_106 {

    private Map<Integer, Integer> inorderIndexMap; // 中序遍历索引哈希表
    private int[] postorder; // 前序遍历数组

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        inorderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }

        return build(0, inorder.length - 1, 0, postorder.length - 1);
    }

    /**
     * 递归构造二叉树
     * @param inStart 中序遍历开始下标
     * @param inEnd 中序遍历结束下标
     * @param postStart 后序遍历开始下标
     * @param postEnd 后序遍历结束下标
     * @return
     */
    private TreeNode build(int inStart, int inEnd,int postStart, int postEnd){
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }

        // 找到当前树的根节点，后序遍历的右区间
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);

        int rootIndex = inorderIndexMap.get(rootVal);
        // 左子树的长度
        int rootLeftSize = rootIndex - inStart;

        // 构造左子树
        root.left = build(
                inStart,
                rootIndex -1,
                postStart,
                postStart + rootLeftSize -1
        );
        // 构造右子树
        root.right = build(
                rootIndex + 1,
                inEnd,
                postStart + rootLeftSize,
                postEnd - 1
        );

        return root;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
